分块,就是一种优雅的暴力。它可以将 的暴力变成
一、如何实现分块
如图:
实现:
int n, T; scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", A + i); // 数组
t = sqrt(n); // 块长
for (int i = 1; i <= t; i++) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
} // L 表示块的左边界, R表示块的右边界
if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
for (int i = 1; i <= t; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i; // pos[j]表示第j个数所处的块的位置
sum[i] += A[j]; // sum[i]表示第i个块的和
}
}
二、如何实现加法
如果让你在 之间的每个数都加上 ,对块进行如图操作(这里 ):
实现:
void upd(int l, int r, LL val) {
if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
else {
for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
}
}
三、如何实现查询
如果让你在 之间的每个数都加上 ,对块进行如图操作(这里 ):
实现:
LL query(int l, int r) {
LL ret = 0ll;
if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
else {
for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
}
return ret;
}
总体实现(例题 P3372):
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
LL A[N], sum[N], tag[N];
int pos[N], L[N], R[N], t;
void upd(int l, int r, LL val) {
if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
else {
for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
}
}
LL query(int l, int r) {
LL ret = 0ll;
if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
else {
for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
}
return ret;
}
int main() {
int n, T; scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", A + i);
t = sqrt(n);
for (int i = 1; i <= t; i++) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
for (int i = 1; i <= t; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
sum[i] += A[j];
}
}
LL k;
for (int op, l, r; T--; ) {
scanf("%d%d%d", &op, &l, &r);
if (op == 1) scanf("%lld", &k), upd(l, r, k);
else printf("%lld\n", query(l, r));
}
return 0;
}
四、如何插入元素
如果让你在位置 插入一个元素,你可以在每一个块内弄一个双端队列,固定块长,如图(以 为例):
将 从第二个块的末尾弹出,进入第三个块的前端, 、 同理。这里显然不能直接手写 ,所以可以用 中的 来实现插入元素和单点查询,复杂度 (插入 ,从 中暴力查询 )。
如果想要手写 ,可以开一个 倍块长的数组,如下表进行操作:
开始时:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 5 | 6 | 7 | 8 |
第 次:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 4 | 5 | 6 | 7 |
第 次:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 3 | 4 | 5 | 6 |
第 块长()次:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 |
当到头了的时候,我们可以将其暴力放到末尾:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 |
一次暴力的复杂度时 ,但这需要 次操作后才可以进行该操作,所以均摊到每次操作上就是 的。
可以发现,这样做可以将查询的时间复杂度降到 ,代码实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
const int Block_Start = 801; // Block_Size = Block_Start
int Size, B[N];
struct per {
int A[Block_Start << 1 | 5], Al = Block_Start, Ar = Block_Start;
per() {Al = Ar = Block_Start;}
void insert(int pos, int val) {
for (int i = Ar - 1; i >= Al + pos - 1; i--) A[i + 1] = A[i];
A[Al + pos - 1] = val; Ar++;
}
void Move_Back() {
if (Al > Block_Start - Size) return;
for (int i = Ar - 1; i >= Al; i--) A[Block_Start - Al + i] = A[i];
int tsz = Ar - Al;
Al = Block_Start; Ar = Al + tsz;
}
int query(int pos) {
return A[Al + pos - 1];
}
}p[505];
LL min(LL x, LL y) {return x < y ? x : y;}
LL max(LL x, LL y) {return x > y ? x : y;}
void Roll_To_Next_Block(int Block) {
while (p[Block].Ar - p[Block].Al > Size) {
p[Block + 1].A[--p[Block + 1].Al] = p[Block].A[--p[Block].Ar];
p[Block + 1].Move_Back();
Block++;
}
}
void upd(int pos, int val) {
int Block = (pos - 1) / Size + 1;
p[Block].insert(pos - (Block - 1) * Size, val);
Roll_To_Next_Block(Block);
}
int query(int pos) {
int Block = (pos - 1) / Size + 1;
return p[Block].query(pos - (Block - 1) * Size);
}
int main() {
srand((unsigned)time(0));
int n, T; scanf("%d", &n); T = n;
for (int i = 1; i <= n; i++) scanf("%d", B + i);
Size = sqrt(n * 2.5);
for (int i = 1, Block; i <= n; i++) {
Block = (i - 1) / Size + 1;
p[Block].insert(i - (Block - 1) * Size, B[i]);
}
int tot = n;
for (int op, l, r, k; T--; ) {
scanf("%d%d%d%d", &op, &l, &r, &k);
if (op == 0) upd(l, r);
else printf("%d\n", query(r));
}
return 0;
}
感谢观看!